The Discrete Fourier Transform (DFT) is a fundamental operation in digital signal processing and finds applications in image processing, speech processing, radar and many other fields. The DFT of a finite duration sequence of N sample points x(n) , 0.ltoreq.n.ltoreq.N-1, is defined as ##EQU1## which may be conveniently written in the form ##EQU2## where EQU W=e.sup.-j(2 .pi./N)
In the case where x(n) is a sequence of complex numbers of the form c+jd, where c is the real part and d is the imaginary part, a complete direct evaluation of an N-point DFT requires (N-1).sup.2 complex multiplications and N(N-1) complex additions.
The set of processes known as the fast Fourier transform (FFT) consists of a variety of techniques for reducing the time required to compute a discrete Fourier transform. Typically, an N-point DFT (where N is a power of 2) is repeatedly halved until N/2 2-point DFTs are obtained. Each 2-point DFT is then computed by the well-known `butterfly` which performs the operation E.+-.WF, where E and F are complex inputs and W is a complex multiplier. This approach reduces the required computation to the order of N/2 log.sub.2 N complex multiplications and N log.sub.2 N complex additions, a considerable saving when compared with the direct DFT.
The fast Fourier transform class of processes finds applications mostly in general-purpose transformations of large blocks of data such as where N is greater than 1000. Most FFT processors are optimized for the butterfly operation, which requires a complex multiplication and a complex addition and subtraction. This equates to four real multiplications and six real additions, subtraction being considered as the addition of a negative number. To obtain large throughput, it has often been necessary to use more than one multiplier/adder and much additional controller hardware. Some existing FFT processors also require that separate memories be used for real and imaginary data.
The Winograd fast Fourier transform reduces the number of complex operations by providing a multiplier in each butterfly operation which is a pure real or pure imaginary scalar. The processes can be further simplified where all inputs to the processor are either pure real or pure imaginary.
Small FFTs such as an 8-point FFT or a 16-point FFT can be used as building blocks in the overall transform. For example, a 192-point FFT can be based on a set of three 64-point FFTs followed by 64 3-point FFTs. Each 64-point FFT might in turn be based on two stages of FFTs, each stage including eight 8-point FFTs.